/*
 * Copyright (c) 2021
 * User:LENOVO
 * File:搜索旋转排序数组.java
 * Date:2021/02/18 14:17:18
 */

package org.bytedance.数组与排序;

/**
 * 升序排列的整数数组 nums 在预先未知的某个点上进行了旋转（例如， [0,1,2,4,5,6,7] 经旋转后可能变为 [4,5,6,7,0,1,2] ）。
 * <p>
 * 请你在数组中搜索 target ，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/search-in-rotated-sorted-array
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class 搜索旋转排序数组 {

    public static void main(String[] args) {
        搜索旋转排序数组 instance = new 搜索旋转排序数组();
        int[] inputs = new int[]{4, 5, 6, 7, 0, 1, 2};
        int target = 0;
        int search = instance.search(inputs, target);
        System.out.println(search);

        target = 3;
        search = instance.search(inputs, target);
        System.out.println(search);

        inputs = new int[]{1};
        target = 0;
        search = instance.search(inputs, target);
        System.out.println(search);


    }

    public int search(int[] nums, int target) {
        int lo = 0, hi = nums.length - 1;
        while (lo <= hi) {
            int mid = lo + ((hi - lo) >> 1);// 3=>7
            if (nums[mid] == target) return mid;

            if (nums[0] <= nums[mid]) {
                if (nums[0] <= target && target < nums[mid]) {
                    hi = mid - 1;
                } else {
                    lo = mid + 1;
                }
            } else {
                if (nums[mid] < target && target <= nums[nums.length - 1]) {
                    lo = mid + 1;
                } else {
                    hi = mid - 1;
                }
            }
        }

        return -1;
    }
}
